1. Field of the Invention
The present invention relates to the field of computer systems. More specifically, the present invention relates to data block relocation methodology and apparatuses incorporated with such methodology.
2. Background Information
In the art of computer systems, many problems involve relocating data blocks. For examples, in U.S. patent application, Ser. No. 08/708,983, entitled Method and Apparatus For Improving Disk Drive Performance, filed on Sep. 6, 1996, assigned to the assignee of the present invention, certain disk block relocation methodology for improving disk drive performance was disclosed. In particular, a standalone disk block relocation utility incorporated with the disk block relocation methodology was disclosed. In U.S. patent application, Ser. No. 08/721,826, also entitled Method and Apparatus For Improving Disk Drive Performance, filed on Sep. 27, 1996, assigned to the assignee of the present invention, incorporation of the disk block relocation utility into an installation utility of an application for improving the application start up time through disk block relocation was disclosed. In U.S. patent applications, Ser. No. 08/822,640, entitled Reducing Operating System Start Up/Boot Time Through Disk Block Relocation, filed on Mar. 21, 1997, assigned to the assignee of the present invention, partial incorporation of the disk block relocation utility into an operating system for improving the start up/boot time of the operating system was disclosed.
In each case, whether it was the standalone utility, the application installation utility or the complementary function to the operating system, a disk block relocation engine is provided. The disk block relocation engine relocates disk blocks in accordance with a disk block relocation vector, using any one of a number of data moving techniques known in the art, as illustrated by FIG. 1. The data moving technique employed by relocation engine 100 is typically "destination oriented", that is, the data move operations are performed based on the identity of the destination blocks. Thus, relocation vector 102 is also typically "destination oriented".
FIGS. 2A-2D illustrate one such data moving technique, a "destination and swap oriented" technique. Specifically, FIG. 2A illustrates an exemplary collection of disk blocks, disk block B1 through B7, with disk blocks B1-B6 having content A through F, and disk block B7 having no content, i.e. initially empty or unused. FIG. 2B illustrates an exemplary destination oriented disk block relocation vector 102 for exemplary disk blocks B1 through B7. Exemplary disk block relocation vector 102 specifies that the contents of disk blocks B1, B2, B4 and B5 are to be relocated to disk blocks B2, B3, B5 and B6 respectively. In other words, disk block B2 is the destination disk block for the current content of disk block B1, disk block B3 is the destination disk block for the current content of disk block B2, and so forth.
For illustrative purpose, disk blocks B3 and B6 are not among the disk blocks of interest, thus exemplary disk block relocation vector 102 does not specify where the displaced contents of disk blocks B3 and B6 should be moved. Typically, disk block relocation engine 100 would arbitrarily allocate some of the available disk blocks as the destination disk blocks. For illustrative purpose, we will assume the arbitrarily assigned destination disk blocks to be disk blocks B1 and B4. Disk blocks B1 and B4 are available because their contents are going to be moved to disk blocks B3 and B5 respectively.
As illustrated by FIG. 2C, typically, disk block relocation engine 100 would process disk block relocation vector 102 sequentially, one disk block entry at a time. The first disk block entry calls for the content of disk block B1 to be moved to disk block B2. Since B2 is used, the content of B2 is first moved to a staging disk block, e.g. disk block B7, then the content of disk block B1 is moved to the now available disk block B2. After that, the content from the staging area is moved back to the now available disk block B1. In other words, the first three moves are "B2.fwdarw.B7", "B1.fwdarw.B2", then "B7.fwdarw.B1" as shown in FIG. 2c.
The next disk block entry calls for the initial content of disk block B2, which is now in disk block B1, to be moved to disk block B3. So a similar triple moves occur, i.e. "B3.fwdarw.B7", "B1.fwdarw.B3", then "B7.fwdarw.B1" as shown in FIG. 2c. The next disk block entry calls for the initial content of disk block B3, which is now in disk block B1, to be moved to disk block B1. Since the move has already been accomplished, disk block relocation engine 100 moves on to process the next disk block relocation entry, which calls for the initial content of disk block B4, which is still in disk block B4, to be moved to disk block B5. Again a similar triple moves occur, i.e. "B5.fwdarw.B7","B4.fwdarw.B5", then "B7.fwdarw.B4" as shown in FIG. 2c.
The next disk block entry calls for the initial content of disk block B5, which is now in disk block B4, to be moved to disk block B6. So again a similar triple moves occur, i.e. "B6.fwdarw.B7", "B4.fwdarw.B6", then "B7.fwdarw.B4" as shown in FIG. 2c. Finally, the last disk block entry calls for the "pre-move" content of disk block B6, which is now in disk block B4, to be moved to disk block B4. Since the move has already been accomplished and all disk block relocation entries have been processed, disk block relocation engine 100 terminates the relocation process. The desired moves have all been accomplished, resulting in disk blocks B1-B6 storing contents C, A, B, F, D, E respectively, as illustrated in FIG. 2D.
Thus, for the exemplary disk block collection and the exemplary desired disk block relocations, disk block relocation engine 100, using one of the "destination and swap oriented" technique of the art, would require about 12 move operations. Those skilled in the art will recognize that in real life, disk block relocation problems are much more complex than that, requiring hundreds if not thousands of move. Therefore, it is desirable to be able to reduce the number of move operations required to accomplish a given set of data relocation objectives.